home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Chip 1996 April
/
CHIP 1996 aprilis (CD06).zip
/
CHIP_CD06.ISO
/
hypertxt.arj
/
9311
/
CHIPKEDD.CD
< prev
next >
Wrap
Text File
|
1995-04-15
|
9KB
|
150 lines
@VSzerencsés vezérek@N
Augusztusi számunk feladatainak megoldásairól ejtünk az
alábbiakban néhány szót.
De ezt megelôzôen egy helyesbítést kell tennünk:
szeptemberi számunkban tévesen jelent meg júniusi,
Tili-toli címû feladatunk megoldóinak névsora. Tehát immár
helyesen: a feladatra Déri Attila és Verbôczi Zoltán
küldött be jó megoldást. Az érintettektôl és olvasóinktól
elnézést kérünk.
@VSzerencsés számok@N
Egy számot akkor neveztünk szerencsésnek, ha jegyei két
csoportba oszthatók úgy, hogy a két csoportban a számok
összege ugyanannyi, mint például a 32843 esetében
(8+2=3+4+3). A feladat az ""iker" (azaz szomszédos)
szerencsés számokat megkeresô program írása volt.
Megoldásként hét programot kaptunk hat megfejtônktôl. A
Pascal fölénye megkérdôjelezhetetlen, bár mérséklôdött: 4-3
arányban nyert a C elôtt. Természetesen egyéb különbségek
is adódtak a megoldásokban. A többség képenyôre íratta a
megoldásokat, de volt, aki file-ba (Verbôczi Zoltán); a
többség százezerig kereste meg a kívánt számokat, de volt,
aki kilencjegyû számokat is megtalált programjával (a
Bonifert-Fürcht páros programjai); a többség megoldásai nem
mérhetô idô alatt (pontosabban csak ""kiírásnyi" idôt
használva) varázsolták elô az ikreket, de volt olyan
program is, amely négy óra alatt számolt (volna) el
százezerig -- igaz hibátlanul, ellentétben más, némely
ikerpárost ""elfelejtô" programmal.
Egy picit utánagondolva a feltételeknek, rögtön adódik,
hogy egy szerencsés szám jegyeinek összege páros. Ebbôl az
is hamar kitalálható, hogy az iker kisebbik tagjának utolsó
jegye kilences, mivel a ""nagyobbik testvér" jegyösszegének
páros volta csak így biztosítható. Ez persze azt is
jelenti, hogy kétjegyû ikrek nem találhatók, sôt még az is
kiszámolható fejben, hogy a háromjegyû számok körében is
csak egy páros lesz: a 459 és az 550. Innen kezdve viszont
rohamosan szaporodnak az iker szerencsés számok (a hamar
megvizsgálható százezres határig 984 darab pár található).
Megtalálásukhoz segítséget nyújthatott májusi,
részhalmazokról szóló feladatunk; hiszen itt is nagyjából
arról volt szó, hogy a számjegyek sorozatának minden
lehetséges részsorozatát képezve, megkapjuk-e az összeg
felét. Érdekes eltérések adódtak a programokban a
számjegyek elôállítási módjában: volt, aki matematikai
mûveleteket (div, mod) használt; volt aki stringekké
konvertálva szeletelt; s volt, aki megfordítva a kérdést,
egy tömbben tárolt jegyekbôl képezte a számokat (ez esetben
persze jobban oda kellett figyelni a megfelelô léptetésre).
A CT Press BBS-en mindkét nyelv híveinek található
megoldás: Verbôczi Zoltán Pascal, és Bonifert Csaba-Fürcht
Zoltán C nyelven írott programja olvasható ott. A szerencse
-- egy doboz Tungsram flopy formájában -- Déri Attila
olvasónkat vonta kegyeiben.
@VVezérek másképpen...@N
...címmel megjelent feladatunk egy olyan program írását
kívánta meg, amely elhelyez a 8x8-as sakktáblán minél
kevesebb királynôt úgy, hogy azok a tábla minden mezôjét
ütés alatt tartsák. A megoldások száma ""mesés": hét
megfejtônk hét programot küldött be (itt a Pascal kontra C
mérkôzés eredménye 5-2 lett). Az tiviálisan adódik az egy
vezér által maximálisan ""fogható" mezôk számából, hogy egy
illetve két vezér nem lesz elegendô. Az is sejthetô, hogy
innen kezdve viszont az idô lesz a szûk keresztmetszet:
hiszen már három vezér is 41664 variációban helyezhetô el a
8x8-as táblán, de négy vezér már 635376, öt pedig 7624512
lehetôséget jelent. Megfejtôink jól hidalták át ezt a
nehézséget: a beküldött programok 2-8 perc alatt
szolgáltattak egy-egy megoldást a szükséges öt vezér
elhelyezésére (386SX gépen futtatva). Ennél sokkal tovább
mûködött Verbôczi Zoltán programja: ennek azonban az volt
az oka, hogy nemcsak egy elrendezést adott meg, hanem az öt
vezér összes megfelelô elhelyezését megkereste! (Ezek száma
4860 -- nem véve figyelembe a lehetséges tükrözéseket,
forgatásokat).
Két lehetséges megoldási utat ismertetünk olvasóink leírása
nyomán. Déri Attila: ""Rekurzív eljárással keresem meg a
királynôk helyét. Az eljárás a legutoljára lerakott
királynô 'utáni' mezôbe lerak egy királynôt, s megnézi,
hogy minden mezô fogott-e. Ha nem, és a lerakott királynôk
száma nem haladja meg az eddigi minimumot, akkor meghívja
önmagát. Ha minden mezô ütés alatt áll, akkor elmenti az
állást. A lerakott királynôt felveszi, s a következô mezôbe
téve, újra vizsgálja az állást a tábla végéig menve. A
rekurzív eljárás végén a program kiírja az elmentett
állást." Más utat választott Horváth Sándor: ""A sakktábla
minden mezôjéhez egy 64 bites számot rendelhetünk, amely
jelzi, hogy onnan a tábla mely mezôi tarthatók ütés alatt.
(...) E számok (64 db 64 bites érték) segítségével nagyon
könnyen eldönthetô, hogy a táblán elhelyezett néhány vezér
ütésben tartja-e az egész táblát: a vezérekhez tartozó
értékeket a logikai OR mûvelettel ""összeadjuk". Ha az így
kapott 64 bit mindegyike 1-es, akkor a vezérek lefedik a
táblát. (A Pascalban igazi 64 bites egész típus nem lévén,
két 32 bites longintbôl kellett összerakni egy 64 bites
""számot"). Az összes eset elôállításához a halmaz
részhalmazainak elôállításánál használt algoritmust vettem
át egy az egyben (megint a májusi feladat!), melyhez egy 64
byte-os stringben tároltam a tábla elrendezését."
A CT Press BBS-en Verbôczi Zoltán és Déri Attila programja
található meg. Természetesen az eddigiekben név szerint nem
említett megfejtôink (Bonifert Csaba-Fürcht Zoltán, Tóth
László, Balla Attila) is részesei az év végi sorsolásnak.
Végezetül a feladat egy megoldása: A2, C1, D6, D7, H1.
@KBánhegyesi Zoltán@N
@Vùj rejtvényünk@N
@VMersenne-prímek@N
A Bild der Wissenschaft tavaly novemberi számában jelent
meg egy híradás egy újabb prímrekordról: Michael Stromberg
megtalálta az eddig ismert legnagyobb prímet, amelynek
értéke
2^756839-1. Ezt a 227832 jegyû számot magazinunk majd'
félévig közölhetné folyamatosan, összes oldalán! Mint a
cikkbôl is kiderül, Stromberg egy közel háromszázötven éves
úton indult el. Mersenne francia matematikus 1644-ben
közölte, hogy a
2^p-1 kifejezés értéke 1 < p < 258 számok esetén csak a p =
2, 3, 5, 7, 13, 17, 19, 31, 67, 127 és 257 értékénél prím.
A matematikusok háromszáz év alatt tisztázták, hogy a lista
hibás: tartalmaz összetett számokat, s nem minden prímre
vezetô értéket adott meg Mersenne.
A feladat egy olyan program írása, mely háromszáz évnél
némileg rövidebb idô alatt megtalálja a hibákat Mersenne
listájában.
Beküldési határidô: 1993 december 3.
@KBánhegyesi Zoltán@N